package leetcode.weekly.week307;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

//Solution4Test
public class Solution4 {
	
	public long kSum(int[] nums, int k) {
		long sum = 0;
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] > 0) {
				sum += nums[i];
			} else {
				nums[i] = -nums[i];
			}
		}
		Arrays.sort(nums);
		PriorityQueue<long[]> queue = new PriorityQueue<>((a, b) -> Long.compare(b[0], a[0]));
		queue.add(new long[] { sum, 0L });
		queue.offer(null);
		for (int i = 1; i < k; i++) {
			long[] cur = queue.poll();
			if (cur[1] < nums.length) {
				if (cur[1] > 0)
					queue.add(new long[] { cur[0] - nums[(int) cur[1]] + nums[(int) cur[1] - 1], cur[1] + 1 });
				queue.add(new long[] { cur[0] - nums[(int) cur[1]], cur[1] + 1 });
			}
		}
		// [2,4,-2]
		// 6、4、4、2、2、0、0、-2
		return queue.peek()[0];
	}

	public long kSumOK(int[] nums, int k) {
		long sum = 0;
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] > 0) {
				sum += nums[i];
			} else {
				nums[i] = -nums[i];
			}
		}
		Arrays.sort(nums);
		PriorityQueue<long[]> queue = new PriorityQueue<>((a, b) -> Long.compare(b[0], a[0]));
		queue.add(new long[] { sum, 0L });
		queue.offer(null);
		for (int i = 1; i < k; i++) {
			long[] cur = queue.poll();
			if (cur[1] < nums.length) {
				if (cur[1] > 0)
					queue.add(new long[] { cur[0] - nums[(int) cur[1]] + nums[(int) cur[1] - 1], cur[1] + 1 });
				queue.add(new long[] { cur[0] - nums[(int) cur[1]], cur[1] + 1 });
			}
		}
		// [2,4,-2]
		// 6、4、4、2、2、0、0、-2
		return queue.peek()[0];
	}

	public long kSum1(int[] nums, int k) {
		long sum = 0;
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] > 0) {
				sum += nums[i];
			} else {
				nums[i] = -nums[i];
			}
		}
		Arrays.sort(nums);
		PriorityQueue<long[]> queue = new PriorityQueue<>((a, b) -> Long.compare(b[0], a[0]));
		queue.add(new long[] { sum - nums[0], 0L });
		for (int i = 2; i < k; i++) {
			long[] cur = queue.poll();
			System.out.println(cur[0] + " " + cur[1]);
			if (cur[1] < nums.length) {
				System.out.println(cur[0] - nums[(int) cur[1]] + " " + (cur[1] + 1));
				if (cur[1] < nums.length - 1) {
					queue.add(new long[] { cur[0] - nums[(int) cur[1] + 1] + nums[(int) cur[1]], cur[1] + 1 });
					queue.add(new long[] { cur[0] - nums[(int) cur[1] + 1], cur[1] + 1 });
				}
			}
		}
		// [2,4,-2]
		// 6、4、4、2、2、0、0、-2
		return queue.peek()[0];
	}

}
